

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <unordered_map>
using namespace std;

class Solution
{
public:
    bool canConstruct1(string ransomNote, string magazine)
    {
        if (ransomNote.size() > magazine.size())
            return false;

        int cnt1[26] = { 0 };
        int cnt2[26] = { 0 };

        for (const auto s : ransomNote)
        {
            ++cnt1[s - 'a'];
        }
        for (const auto s : magazine)
        {
            ++cnt2[s - 'a'];
        }

        for (int i = 0; i < 26; ++i)
        {
            if (cnt1[i] > cnt2[i])
                return false;
        }

        return true;
    }

    bool canConstruct2(string ransomNote, string magazine)
    {
        if (ransomNote.size() > magazine.size())
            return false;

        unordered_map<char, int> hash;

        for (const auto ch : magazine)
        {
            ++hash[ch];
        }
        for (const auto ch : ransomNote)
        {
            if (!hash[ch])
                return false;
            else
                --hash[ch];
        }

        return true;
    }

    bool canConstruct3(string ransomNote, string magazine)
    {
        if (ransomNote.size() > magazine.size())
            return false;

        int cnt[26] = { 0 };

        for (const auto s : magazine)
        {
            ++cnt[s - 'a'];
        }

        for (const auto s : ransomNote)
        {
            if (--cnt[s - 'a'] < 0)
                return false;
        }

        return true;
    }

    int bulbSwitch(int n)
    {
        return sqrt(n);
    }
};

void Test1()
{
    cout << sqrt(5) << endl;
    cout << Solution().canConstruct2("aa", "ab") << endl;
}

int solution(vector<vector<int>>& matrix, int target)
{
    int res = 0;
    int n = matrix.size();
    int m = matrix[0].size();
    vector<vector<int>> ans(n + 1, vector<int>(m + 1, 0));

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            ans[i + 1][j + 1] = matrix[i][j] + ans[i][j + 1] + ans[i + 1][j] - ans[i][j];
        }
    }

    for (int top = 0; top < n; top++)
    {
        for (int bottom = top; bottom < n; bottom++)
        {
            unordered_map<int, int> sumCount;
            sumCount[0] = 1;
            for (int col = 0; col < m; col++)
            {
                int currentSum = ans[bottom + 1][col + 1] - ans[top][col + 1];
                if (sumCount.find(currentSum - target) != sumCount.end())
                    res += sumCount[currentSum - target];

                sumCount[currentSum]++;
            }
        }
    }

    return res;
}

void Test2() 
{
    vector<vector<int>> v1 = { {-1, 1, 0}, {1, 1, 1}, {0, 1, 0} };
    vector<vector<int>> v2 = { {-1, -1}, {-1, 1} };
    vector<vector<int>> v3 = { {-1, 2, 3}, {4, 5, 6}, {7, 8, 9} };

    cout << (solution(v1, 0) == 7) << endl;
    cout << (solution(v2, 0) == 2) << endl;
    cout << (solution(v3, 10) == 2) << endl;
}

int main()
{
    //Test1();
    Test2();

	return 0;
}